/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/lru-cache
   @Language: C++
   @Datetime: 16-12-09 09:59
   */

// Method 1, Using STL list, Time 97ms
// The Most serious point is that this problem code do not include <list>,
// Althought using #include <list> can pass it, the owner of this problem
// do not want us use STL list.
#include <list>
class LRUCache{
	int capacity;
	list<pair<int,int> > lrulist;
	unordered_map<int,list<pair<int,int> >::iterator> cache;

	void update(int key, int val){
		if (cache.find(key)!=cache.end())
			lrulist.erase(cache[key]);
		lrulist.push_front(make_pair(key,val));
		cache[key]=lrulist.begin();
	}

public:
	// @param capacity, an integer
	LRUCache(int capacity) {
		// write your code here
		this->capacity = capacity;
		lrulist.clear();
		cache.clear();
	}

	// @return an integer
	int get(int key) {
		// write your code here
		const auto &f = cache.find(key);
		if (f==cache.end()) return -1;
		update(key,f->second->second);
		return cache[key]->second;
	}

	// @param key, an integer
	// @param value, an integer
	// @return nothing
	void set(int key, int value) {
		// write your code here
		if (cache.find(key)==cache.end() && cache.size()==capacity){
			cache.erase(lrulist.back().first);
			lrulist.pop_back();
		}
		update(key,value);
	}
};

// Method 2, Using user-define Double List, Time 97ms
class LRUCache{
	// user-define delist
	template<typename T>
	class delist{
		struct Node{
			T val;      // double link node
			Node *prev, *next;
			Node(const T &t){
				val = t;
				prev = next = NULL;
			}
		};
		Node *front, *tail;
		
	public:
		typedef T* iterator;
		delist() {front=tail=NULL;}
		~delist() {clear();}
		void push_front(const T &t){
			Node *p = new Node(t);
			if (front){
				front->prev = p;
				p->next = front;
			}
			else tail = p;
			front = p;
		}
		void pop_back(){
			if (!tail) return;
			if (front==tail){
				delete tail;
				tail = front = NULL;
			}
			else{
				tail = tail->prev;
				delete tail->next;
				tail->next = NULL;
			}
		}
		void erase(iterator it){
			if (!it) return;
			// like linux container_of()
			// it is the point of typename T val, 
			// which is the member in struct Node,
			// to get the whole point of struct Node.
			const Node *p = (Node*)((char*)it-((size_t)&((Node*)0)->val));

			if (p->prev) p->prev->next = p->next;
			if (p->next) p->next->prev = p->prev;
			if (front==p) front = p->next;
			if (tail==p) tail = p->prev;
			delete p;
		}
		void clear(){
			while(front){
				tail = front;
				front = front->next;
				delete tail;
			}
			front=tail=NULL;
		}
		iterator begin(){ return &front->val;}
		iterator end()  { return NULL;}
		T& back() { return tail->val;}
	};      // user-define delist

	int capacity;
	delist<pair<int,int> > lrulist;
	unordered_map<int,delist<pair<int,int> >::iterator> cache;
	// From below code are same as Method 1.
	void update(int key, int val){
		if (cache.find(key)!=cache.end())
			lrulist.erase(cache[key]);
		lrulist.push_front(make_pair(key,val));
		cache[key]=lrulist.begin();
	}
	
public:
	// @param capacity, an integer
	LRUCache(int capacity) {
		// write your code here
		this->capacity = capacity;
		lrulist.clear();
		cache.clear();
	}

	// @return an integer
	int get(int key) {
		// write your code here
		const auto &f = cache.find(key);
		if (f==cache.end()) return -1;
		update(key,f->second->second);
		return cache[key]->second;
	}

	// @param key, an integer
	// @param value, an integer
	// @return nothing
	void set(int key, int value) {
		// write your code here
		if (cache.find(key)==cache.end() && cache.size()==capacity){
			cache.erase(lrulist.back().first);
			lrulist.pop_back();
		}
		update(key,value);
	}
};
